package greedy;

import java.util.PriorityQueue;

/**
 * @author tongchen
 * @create 2023-03-12 14:05
 * 金条问题的贪心算法
 */
public class LessMoney {
    public static int lessMoney(int[]arr){
        //这个问题的贪心算法在于类似于哈夫曼树
        //建立小根堆不断从中读取
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        //将金条的数值加入
    for(int i=0;i< arr.length;++i){
        queue.add(arr[i]);
    }
    int cur=0;
     int sum=0;
    //不断循环取出
        while(queue.size()>1){
            //拿出两个值，然后将其中一个值再放入
            cur=queue.poll()+queue.poll();
            sum+=cur;
            queue.add(cur);
        }
        return sum;
    }
}
